/**
 * 第一问就是问不严格最长下降子序列
 * 第二问问整个数组最少可以划分为多少个不严格下降子序列
 * 本质上就是问严格最长上升子序列
 * 要用NlogN算法
 */
#include <bits/stdc++.h>
using namespace std;

int N;
int A[100010];
int B[100010],C[100010];

int main(){
    //freopen("1.txt","r",stdin);
    while(EOF!=scanf("%d",A+N)) ++N;

    //第一问相当于求一个不严格最长下降子序列
    //第二问相当于求一个严格最长上升子序列
    int br = 1, cr = 1;
    B[1] = C[1] = A[0];
    for(int i=1;i<N;++i){
        if ( A[i] <= B[br] ) {
            B[++br] = A[i];
        }else{
            *lower_bound(B+1,B+br+1,A[i],greater_equal<int>()) = A[i];
        }
        if ( C[cr] < A[i] ) C[++cr] = A[i];
        else *lower_bound(C+1,C+cr+1,A[i]) = A[i];
    }

    printf("%d\n%d\n",br,cr);
    return 0;
}